package com.moon.homework.java;

import java.time.Duration;
import java.time.LocalDateTime;
import java.util.Arrays;
import java.util.Random;
import java.util.concurrent.ThreadLocalRandom;

public class SortUtils {

    private static final ThreadLocalRandom RANDOM = ThreadLocalRandom.current();

    public static void main(String[] args) {
        int length = 100000;
        int[] array = initArray(-1 * length, length, length);
        int[] copyArray = new int[length];
        System.arraycopy(array, 0, copyArray, 0, array.length);

        System.out.println("数组长度: " + array.length);

        LocalDateTime startTime = LocalDateTime.now();
        SortUtils.quickSort(copyArray);
        LocalDateTime endTime = LocalDateTime.now();
        long duration = Duration.between(startTime, endTime).toMillis();
        System.out.printf("单线程快速排序耗时: %ss\n", duration/1000d);
        System.out.println("是否有序: " + SortUtils.isSorted(copyArray));
        System.out.println("---------------------------");

        // 单线程希尔排序
        startTime = LocalDateTime.now();
        SortUtils.radixSort(array);
        endTime = LocalDateTime.now();
        duration = Duration.between(startTime, endTime).toMillis();
        System.out.printf("单线程基数排序耗时: %ss\n", duration/1000d);
        System.out.println("是否有序: " + SortUtils.isSorted(array));
        System.out.println("---------------------------");
    }

    /**
     * 生成[min, max]范围内的随机数数组
     *
     * @param min 最小值
     * @param max 最大值
     * @param num 随机数个数
     * @return 随机数数组
     */
    public static int[] initArray(int min, int max, int num) {
        int[] array = new int[num];
        Random random = new Random();
        // random.setSeed(System.currentTimeMillis());
        for (int i = 0; i < num; i++) {
            array[i] = random.nextInt(max - min + 1) + min;
        }
        return array;
    }

    /**
     * 交换数组下标为a和b的元素
     * @param array 数组
     * @param a     下标
     * @param b     下标
     */
    public static void swap(int[] array, int a, int b) {
        int temp = array[a];
        array[a] = array[b];
        array[b] = temp;
    }

    /**
     * 比较两个数组的元素是否完全相同
     * @param array 数组1
     * @param dest  数组2
     * @return true相同 false不同
     */
    public static boolean isEqual(int[] array, int[] dest) {
        if (array.length != dest.length) {
            return false;
        }
        int length = array.length;
        for (int i = 0; i < length; i++) {
            if (array[i] != dest[i]) {
                return false;
            }
        }
        return true;
    }

    /**
     * 快速排序
     *
     * @param array 待排序数组
     */
    public static void quickSort(int[] array) {
        quickSort(array, 0, array.length - 1);
    }

    /**
     * 快速排序
     *
     * @param array   待排序数组
     * @param lowPtr  排序区间的最小索引
     * @param highPtr 排序区间的最大索引
     */
    public static void quickSort(int[] array, int lowPtr, int highPtr) {
        if (lowPtr >= highPtr) {
            return;
        }

        int pivot = partition(array, lowPtr, highPtr);
        quickSort(array, lowPtr, pivot - 1);
        quickSort(array, pivot + 1, highPtr);
    }

    /**
     * 选择最右端位置的数字作为枢纽, 最终返回枢纽排序后的位置
     * @param array   待排序数组
     * @param lowPtr  排序区间的最小索引
     * @param highPtr 排序区间的最大索引
     * @return 枢纽位置
     */
    private static int partition(int[] array, int lowPtr, int highPtr) {
        int x = array[highPtr];
        int i = lowPtr - 1;
        int j = lowPtr;
        while (j < highPtr) {
            if (array[j] < x) {
                i++;
                SortUtils.swap(array, i, j);
            }
            j++;
        }
        i++;
        SortUtils.swap(array, i, highPtr);
        return i;
    }

    /**
     * 随机快速排序
     * @param arrays 待排序数组
     */
    public static void randomizedQuickSort(int[] arrays) {
        randomizedQuickSort(arrays, 0, arrays.length - 1);
    }

    /**
     * 随机快速排序
     *
     * @param arrays  待排序数组
     * @param lowPtr  排序区间的最小索引
     * @param highPtr 排序区间的最大索引
     */
    public static void randomizedQuickSort(int[] arrays, int lowPtr, int highPtr) {
        if (lowPtr < highPtr) {
            int partition = randomizedPartition(arrays, lowPtr, highPtr);
            randomizedQuickSort(arrays, lowPtr, partition - 1);
            randomizedQuickSort(arrays, partition + 1, highPtr);
        }
    }

    /**
     * 随机化划分
     *
     * @param array   待排序数组
     * @param lowPtr  最小索引
     * @param highPtr 最大索引
     * @return 随机划分元素的最终索引位置
     */
    private static int randomizedPartition(int[] array, int lowPtr, int highPtr) {
        // System.out.println(lowPtr+ " " + highPtr);
        int i = RANDOM.nextInt(highPtr - lowPtr + 1) + lowPtr;
        SortUtils.swap(array, i, highPtr);
        return partition(array, lowPtr, highPtr);
    }

    /**
     * 判断数组是否从小到大有序
     * @param array 数组
     * @return true有序 false无序
     */
    public static boolean isSorted(int[] array) {
        return isSorted(array, 0, array.length - 1);
    }

    /**
     * 判断数据区间是否有序
     * @param array 数组
     * @param low 数据区间的最小索引
     * @param high 数据区间的最大索引
     * @return true有序 false无序
     */
    public static boolean isSorted(int[] array, int low, int high) {
        for (int i = low; i < high; i++) {
            if (array[i] > array[i + 1]) {
                return false;
            }
        }
        return true;
    }

    /**
     * 归并排序
     *
     * @param array 待排序数组
     */
    public static void mergeSort(int[] array) {
        int length = array.length;
        int[] aux = new int[length];
        mergeSort(array, 0, length - 1, aux);
    }

    /**
     * 归并排序
     *
     * @param arr  待排序数组
     * @param low  待排序数据区间的最小索引
     * @param high 待排序数据区间的最大索引
     * @param aux  与待排序数组等长的数组
     */
    public static void mergeSort(int[] arr, int low, int high, int[] aux) {
        if (low >= high) {
            return;
        }
        int mid = (low + high) / 2;
        mergeSort(arr, low, mid, aux);
        mergeSort(arr, mid + 1, high, aux);
        if (arr[mid] > arr[mid + 1]) {
            merge(arr, low, high, aux);
        }
    }

    /**
     * 合并
     *
     * @param arr  待排序数组
     * @param low  待排序数据区间的最小索引
     * @param high 待排序数据区间的最大索引
     * @param aux  与待排序数组等长的数组
     */
    public static void merge(int[] arr, int low, int high, int[] aux) {
        int mid = (high + low) >> 1;
        mergeArray(arr, low, mid, high, aux);

        // int leftPtr = low;
        // int mid = (high + low) >> 1;
        // int rightPtr = mid + 1;

        // for (int k = low; k <= high; k++) {
        //     aux[k] = arr[k];
        // }
        // for (int k = low; k <= high; k++) {
        //     if (leftPtr > mid) {
        //         arr[k] = aux[rightPtr++];
        //     } else if (rightPtr > high) {
        //         arr[k] = aux[leftPtr++];
        //     } else if (aux[leftPtr] <= aux[rightPtr]) {
        //         arr[k] = aux[leftPtr++];
        //     } else {
        //         arr[k] = aux[rightPtr++];
        //     }
        // }
    }

    /**
     * 合并两个有序数组区间
     * @param arr 待排序数组
     * @param low 最小索引
     * @param mid 中间位置索引
     * @param high 最大索引
     * @param aux 与待排序数组等长的数组
     */
    public static void mergeArray(int[] arr, int low, int mid, int high, int[] aux){
        int leftPtr = low;
        int rightPtr = mid + 1;
        for (int k = low; k <= high; k++) {
            aux[k] = arr[k];
        }
        for (int k = low; k <= high; k++) {
            if (leftPtr > mid) {
                arr[k] = aux[rightPtr++];
            } else if (rightPtr > high) {
                arr[k] = aux[leftPtr++];
            } else if (aux[leftPtr] <= aux[rightPtr]) {
                arr[k] = aux[leftPtr++];
            } else {
                arr[k] = aux[rightPtr++];
            }
        }
    }



    /**
     * 选择排序
     * @param array 待排序数组
     */
    public static void selectSort(int[] array) {
        int length = array.length;
        // 记录每一轮循环的最小数据的索引
        int minIndex;

        for (int i = 0; i < length - 1; i++) {
            minIndex = i;
            for (int j = i + 1; j < length; j++) {
                if (array[minIndex] > array[j]) {
                    minIndex = j;
                }
            }
            // 交换minIndex对应的元素和i对应元素的位置
            swap(array, minIndex, i);
        }
    }

    /**
     * 展示数组
     * @param array 数组
     */
    public static void display(int[] array) {
        System.out.println(Arrays.toString(array));
    }

    /**
     * 基数排序
     * @param array 待排序数组
     */
    public static void radixSort(int[] array){
        radixSort(array, 0, array.length - 1);
    }

    /**
     * 基数排序
     * @param array 待排序数组
     * @param low 数据区间的最小索引
     * @param high 数据区间的最大索引
     */
    public static void radixSort(int[] array, int low, int high) {
        // 位数
        int m = 100;
        // 设置桶个数为20,依次保存-9,-8,...-0(负数的0),+0(正数的0),1,2,...,9的个数
        int size = 20;
        //桶的容器
        int[][] container = new int[size][high-low+1];
        // 桶计数器,表示每个桶有几个元素
        int[] counter = new int[size];

        // 从个位开始比较, a/d%10取当前位的值
        int d = 1;
        boolean loop = true;
        for (int i = 0; i < m; i++) {
            loop = false;
            // 每一次比较前先将桶中元素个数置零
            for (int j = 0; j < size; j++) {
                counter[j] = 0;
            }

            for (int j = low; j <= high; j++) {
                int val = array[j] / d;
                // 有一个val不为0, 表示数据的位数还没有循环到最大
                if (val != 0) {
                    loop = true;
                }
                int v = val % 10;
                int loc;
                if (array[j] >= 0) {
                    loc = 10 + v;
                } else {
                    loc = 9 + v;
                }
                // System.out.println("v: " + v + " loc: " +loc);
                // 存放到对应的桶中
                container[loc][counter[loc]] = array[j];
                // 桶中元素个数加1
                counter[loc]++;
            }

            // 判断是否可以跳出循环, 位数已经循环到最大.
            if (!loop) {
                break;
            }

            // 依次把桶中的数据放回原数组
            int num = low;
            for (int j = 0; j < size; j++) {
                int[] bucket = container[j];
                int bucketLength = counter[j];
                for (int k = 0; k < bucketLength; k++) {
                    // System.out.println("num: " + num + " k:" + k + " j = "+j);
                    array[num++] = bucket[k];
                }
            }

            // display(array);
            // 准备进入下一位比较
            d *= 10;
            /*if (!loop) {
                System.out.println(i);
            }*/
        }
    }

    /**
     * 希尔排序:插入排序的升级版
     * 调大间隔h
     * h=3h+1
     * 最后一次就是插入排序
     * @param array 待排序数组
     */
    public static void shellSort(int[] array){

        int out,in;
        int h = 1;
        int temp;
        int length = array.length;
        while(h < length/3){
            h = 3 * h + 1;
        }

        // 间隔为h的插入排序.
        while(h > 0){
            for(out = 1; out < length; out++){
                temp = array[out];
                in = out;
                while(in > h-1 && array[in-h] > temp){
                    array[in] = array[in-h];
                    in -= h;
                }
                array[in] = temp;
            }
            h = (h-1)/3;
        }
    }
}
